from collections import defaultdict
from typing import List
# 思路： 两次翻转等于一次旋转
# (i,j)→(j,n−1−i) 可以通过两次翻转操作得到：
# (i,j)转置 -> (j,i)行翻转 -> (j,n−1−i)
# 转置：把矩阵按照主对角线翻转，位于 (i,j) 的元素去到 (j,i)。
# 行翻转：把每一行的内部元素翻转，位于 (j,i) 的元素去到 (j,n−1−i)。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 第一步：转置
        for i in range(n):
            for j in range(i):  # 遍历左下三角
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 第二部：行翻转
        for row in matrix:
            row.reverse()
